#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<deque>
#include<queue>
using namespace std;

class Solution{

    public:

    int ans1(vector<vector<int>>& board){
        int n = board.size();
        unzip.resize(n * n + 1);
        int i, j, k = 1;
        for(i = n-1; i >= 0; i=i-2){
            for(j = 0; j < n; j++){
                unzip[k] = board[i][j];
                k++;
            }
            if(i-1 < 0){
                break;
            }
            for(j = n-1; j >= 0; j--){
                unzip[k] = board[i-1][j];
                k++;
            }
        }

        queue<int> q;
        q.push(1);
        int len = 1;
        while(true){
            ret++;
            while(len > 0){
                int x = q.front();
                q.pop();
                
                len--;
                vector<int> temp;
                for(int i = x; i != x+6; i++){
                    temp.push_back(unzip[i]);
                }
                int max_val = *max_element(temp.begin(), temp.end());
                if(max_val != -1){
                    q.push(max_val);
                }
                if(max_val != x+6){
                    q.push(x+6);
                }
                if(x + 6 >= n*n || max_val == n*n){
                    return ret;
                }
                temp.clear();
            }
            len = q.size();
        }
    }

private:
    vector<int> unzip;
    int ret = 0;
};

void test1(){
    Solution s;
    vector<vector<int>> board = {
        {-1,-1,-1,-1,-1,-1},
        {-1,-1,-1,-1,-1,-1},
        {-1,-1,-1,-1,-1,-1},
        {-1,35,-1,-1,13,-1},
        {-1,-1,-1,-1,-1,-1},
        {-1,15,-1,-1,-1,-1}
    };

    int ret = s.ans1(board);
    cout << ret << endl;
}

void test2(){
    Solution s;
    vector<vector<int>> board = {
        {-1,4,-1},
        {6,2,6},
        {-1,3,-1}
    };

    int ret = s.ans1(board);
    cout << ret << endl;
}

int main(void){
    test1();
    test2();

    return 0;
}